/*
 * @lc app=leetcode.cn id=1220 lang=typescript
 *
 * [1220] 统计元音字母序列的数目
 */

// @lc code=start
function countVowelPermutation(n: number): number {
  const mod = 1e9 + 7;
  // 滚动数组
  // ‘a’,‘e’,‘i’,‘o’,‘u’，代表 j 位置的元音字母的组合数
  const dp = new Array(2).fill(0).map(() => new Array(5).fill(1));

  let i = 2;
  while (i <= n) {
    let pre = i % 2;
    let cur = Number(!pre);
    // a 前面只能有 e，i，u
    dp[cur][0] = (dp[pre][1] + dp[pre][2] + dp[pre][4]) % mod;
    // e 前面只能有 a，i
    dp[cur][1] = (dp[pre][0] + dp[pre][2]) % mod;
    // i 前面只能有 e, o
    dp[cur][2] = (dp[pre][1] + dp[pre][3]) % mod;
    // o 前面只能有 i
    dp[cur][3] = dp[pre][2];
    // u 前面只能有 i, o
    dp[cur][4] = (dp[pre][2] + dp[pre][3]) % mod;
    i++;
  }

  let ans = 0;
  for (let j = 0; j < 5; j++) {
    ans = (ans + dp[i % 2][j]) % mod;
  }

  return ans;
}
// @lc code=end
